﻿//
// Created by Freeman on 2022/2/21.
//

/**
 * 动态规划
 */

#ifndef PAT_EXERCISES_DP_H
#define PAT_EXERCISES_DP_H

#include <vector>

class NumberTower {
    std::vector<std::vector<int>> tower;
    std::vector<std::vector<int>> dist_dp;

public:
    void solve();

private:
    int findLongestRoute(int row, int col);
};

class PAT_A1007 {
public:
    static void solve();
};

/**
 * A1045的最长不下降子序列（Longest Increasing Subsequence, LIS）解法
 */
class PAT_A1045_LIS {
public:
    static void solve();
};

class PAT_A1040 {
public:
    static void solve();
};

// ============================== 参考过题解的问题 ==============================

/**
 * A1045的最长公共子序列（Longest Common Subsequence, LCS）解法
 * 思想：本题允许两个序列在公共部分上产生“冗余”的元素。
 * 相比经典LCS，只需将a[i]==b[j]时dp[i][j]的状态转移方程改为max{dp[i-1][j], dp[i][j-1]} + 1.
 */
class PAT_A1045_LCS {
public:
    static void solve();
};

#endif //PAT_EXERCISES_DP_H